import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:最长公共子序列(二)
 * User: wangxin
 * Date: 2024-12-30
 * Time: 22:02
 */
public class Test2 {
    public String LCS (String s1, String s2) {
        // write code here
        int n = s1.length();
        int m = s2.length();
        int[][] dp = new int[n+1][m+1];
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        if(dp[n][m] == 0){
            return "-1";
        }
        StringBuffer sb = new StringBuffer();
        while(n > 0&&m>0){
            if(s1.charAt(n-1)==s2.charAt(m-1)){
                sb.append(s1.charAt(n-1));
                n--;
                m--;
            }else{
                if(dp[n-1][m] > dp[n][m-1]){
                    n--;
                }else{
                    m--;
                }
            }
        }
        return sb.reverse().toString();
    }
}
